package com.dragon.datastructure.queue;

import java.lang.annotation.Target;

/**
 * 用数组模拟循环队列
 * <p>
 * front: 代表队列的队首元素索引
 * rear: 代表队列将要插入到队尾元素的索引(也就是目前队尾元素的下一个索引)
 * <p>
 * 思路分析:
 * 1.队列为空   front == rear
 * 2.队列已满   (rear + 1) % elementData.length == front
 * 3.入队      rear往后面移动,rear = (rear + 1) % elementData.length
 * 4.出队      front往后面移动 front = (front + 1) % elementData.length
 *
 * @author dragon
 * @since 2019/12/17
 */
public class LoopQueue {

    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 代表队列的队首元素索引
     */
    private int front;

    /**
     * 代表队列将要插入到队尾元素的索引(也就是目前队尾元素的下一个索引)
     */
    private int rear;

    /**
     * 真正存储元素的数组
     */
    private int[] elementData;

    /**
     * 循环队列元素个数
     */
    private int size;


    public LoopQueue(int capacity) {
        if (capacity <= 0) {
            throw new RuntimeException("队列初始化失败，队列长度不能小于或等于0");
        }
        elementData = new int[capacity + 1];
        front = rear = 0;
    }

    public LoopQueue() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 入队，添加元素，调整rear的角标
     */
    public void enqueue(int element) {
        if (isFull()) {
            resize(elementData.length << 1);
        }
        elementData[rear] = element;
        rear = ++rear % elementData.length;
        size++;
    }

    /**
     * 出队列，将队首的元素pop出去，调整front的角标
     */
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int popValue = elementData[front];
        front = ++front % elementData.length;
        --size;

        if (size <= elementData.length >> 2 && elementData.length >> 1 != 0) {
            resize(elementData.length >> 1);
        }

        return popValue;
    }

    /**
     * 看元素
     */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }

        return elementData[(front + 1) % elementData.length];
    }

    private void resize(int newCapacity) {
        int[] newElementData = new int[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newElementData[i] = elementData[(i + front) % elementData.length];
        }
        elementData = newElementData;
        front = 0;
        rear = size;
    }

    /**
     * 队列是否为空,当队尾 == 队首时，代表队列为空
     */
    public boolean isEmpty() {

        return rear == front;
    }

    /**
     * 队列是否已经满了
     */
    public boolean isFull() {

        return (rear + 1) % elementData.length == front;
    }

    /**
     * 获得容量
     */
    public int getCapacity() {
        return this.elementData.length - 1;
    }

    /**
     * 队列的长度大小
     */
    public int size() {

        return this.size;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "ArrayQueue{}";
        }
        StringBuilder sb = new StringBuilder();
        sb.append("front");
        for (int i = front; i < (front + size - 1); i++) {
            sb.append(elementData[i % elementData.length] + "=>");
        }
        sb.append(elementData[rear - 1] + "rear");

        return sb.toString();
    }
}
